9606. Modular division

 

Three positive integers a, b and n are given. Compute the value of a / b mod n. In other words, find a value x such that b * x = a mod n.

 

Input. Three positive integers a, b, n (n ≤ 2 * 109, 1 ≤ a, b < n). It is known that n is a prime number.

 

Output. Print the value of a / b mod n.

 

Sample input 1

Sample output 1

3 4 7

6

 

 

Sample input 2

Sample output 2

4 8 13

7

 

 

SOLUTION

exponentiation

 

Algorithm analysis

Since the number n is prime, by Fermat's Little Theorem, the equality bn-1 mod n = 1 holds for any b where 1 ≤ b < n. This equality can be rewritten as (b * bn-2) mod n = 1, which implies that the multiplicative inverse of b is y = bn-2 mod n. Consequently, a / b mod n = a * b-1 mod n = a * y mod n.

The multiplicative inverse can also be found using the extended Euclidean algorithm. To do this, one needs to solve the congruence ax = 1 (mod n). Consider the Diophantine equation

ax + ny = 1

and find its particular solution (x0, y0) using the extended Euclidean algorithm. Taking the equation ax0 + ny0 = 1 modulo n, we get ax0 = 1 (mod n). If x0 is negative, n should be added to it. Thus, x0 = a-1 (mod n) is the multiplicative inverse of a.

 

Example

Let’s consider the second sample. We need to compute 4 / 8 mod 13. To do this, we should solve the equation 8 * x = 4 mod 13, from which it follows that x = (4 * 8-1) mod 13.

Since the number 13 is prime, by Fermat’s Little Theorem, it follows that 812 mod 13 = 1 or (8 * 811) mod 13 = 1. Therefore, 8-1 mod 13 = 811 mod 13 = 5.

Compute the answer: x = (4 * 8-1) mod 13 = (4 * 5) mod 13 = 20 mod 13 = 7.

 

Algorithm realization

The function powmod computes the value of xn mod m.

 

long long powmod(long long x, long long n, long long m)

{

  if (n == 0) return 1;

  if (n % 2 == 0) return powmod((x * x) % m, n / 2, m);

  return (x * powmod(x, n - 1, m)) % m;

}

 

The main part of the program. Read the input data.

 

scanf("%lld %lld %lld", &a, &b, &n);

 

Calculate the values y = bn-2 mod n, x = a * y mod n.

 

y = powmod(b, n - 2, n);

x = (a * y) % n;

 

Print the answer.

 

printf("%lld\n", x);

 

Algorithm realization – the Extended Euclidean algorithm

 

#include <stdio.h>

 

long long a, b, n, d, x, y, inv, res;

 

void gcdext(long long a, long long b,

            long long &d, long long &x, long long &y)

{

  if (b == 0)

  {

    d = a; x = 1; y = 0;

    return;

  }

 

  gcdext(b, a % b, d, x, y);

 

  long long s = y;

  y = x - (a / b) * y;

  x = s;

}

 

int main(void)

{

  scanf("%lld %lld %lld", &a, &b, &n);

  // b * inv + n * y = 1

  gcdext(b, n, d, inv, y);

  if (inv < 0) inv += n;

  res = (a * inv) % n;

  printf("%lld\n", res);

  return 0;

}

 

Python realization

The main part of the program. Read the input data.

 

a, b, n = map(int, input().split())

 

Calculate the values y = bn-2 mod n, x = a * y mod n.

 

y = pow(b, n - 2, n)

x = (a * y) % n

 

Print the answer.

 

print(x)